#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0)return -1;
        if (nums.size() == 1)return nums[0] == target ? 0 : -1;
        int z, y, mid, offset;
        z = 0; y = nums.size() - 1;
        while (z <= y)
        {
            mid = z + y;
            mid /= 2;
            if (nums[mid] >= nums[0])z = mid + 1;
            else y = mid - 1;
        }
        if (mid == nums.size() - 1 && nums[mid - 1] <= nums[mid])mid = 0;
        else
        {
            if (mid < nums.size() - 1 && nums[mid] > nums[mid + 1])mid++;
        }
        offset = mid;
        z = 0; y = nums.size() - 1;
        while (z <= y)
        {
            mid = z + y;
            mid /= 2;
            if (nums[(mid + offset) % nums.size()] == target)break;
            if (nums[(mid + offset) % nums.size()] < target)z = mid + 1;
            else y = mid - 1;
        }
        if (nums[(mid + offset) % nums.size()] == target)return (mid + offset) % nums.size();
        else return -1;
    }
};
int main()
{
    Solution sol;
}